package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-18 14:25
 * @Descriptin: MinPathSum$64-最小路径和-https://leetcode-cn.com/problems/minimum-path-sum/
 */
public class MinPathSum {

	/**
	 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
	 * <p>
	 * 说明：每次只能向下或者向右移动一步。
	 * <p>
	 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
	 * 输出：7
	 * 解释：因为路径 1→3→1→1→1 的总和最小。
	 * 示例 2：
	 * <p>
	 * 输入：grid = [[1,2,3],[4,5,6]]
	 * 输出：12
	 *  
	 * <p>
	 * 提示：
	 * <p>
	 * m == grid.length
	 * n == grid[i].length
	 * 1 <= m, n <= 200
	 * 0 <= grid[i][j] <= 100
	 * <p>
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/minimum-path-sum
	 * <p>
	 * <p>
	 * 【解析】
	 * 【最值型动态规划】
	 * <p>
	 * step 1:确定状态
	 * 无论何种方式到达右下角，总有最后一步，向下或向右
	 * 右下角坐标设置为(m-1,n-1)
	 * 则前一步一定是在(m-2,n-1)或者(m-1,n-2)走来
	 * <p>
	 * 最后一步：
	 * 最优策略的路径总和数字最小：
	 * - 若倒数第二步在（m-2,n-1），则前面一定是从(0,0)到达(m-2,n-1)总和最小的路径
	 * - 若倒数第二步在（m-1,n-2），则前面一定是从(0,0)到达(m-1,n-2)总和最小的路径
	 * 子问题：
	 * 要求从左上角走到（m-1,n-2）的路径的最小数字和以及走到（m-2,n-1）的路径最小数字总和
	 * 原题要求有从左上角走到(m-1,n-1)的路径最小数字总和
	 * 状态：设从(0,0)走到(i,j)的路径最小数字总和f[i][j]
	 * <p>
	 * step 2:转移方程
	 * 设从(0,0)走到(i,j)的路径最小数字总和f[i][j]
	 * f[i][j] = min{f[i-1][j],f[i][j-1]}+A[i][j]
	 * <p>
	 * step 3:初始条件和边界情况
	 * 初始条件：f[0][0] = A[0][0]
	 * 边界情况：i=0或j=0,则前一步只能有一个方向过来
	 * step 4:计算顺序
	 * <p>
	 * f[0][0] = 1;
	 * 计算第0行：  f[0][0],f[0][1],...f[0][n-1]
	 * 计算第1行：  f[1][0],f[1][1],...f[1][n-1]
	 * ...
	 * 计算第m-1行：f[m-1][0],f[m-1][1],...f[m-1][n-1]
	 * <p>
	 * f[i][j] = f[i-1][j]+f[i][j-1]
	 * <p>
	 * 时间复杂度(计算步数)：O(MN),空间复杂度(数组大小)：O(MN)
	 * <p>
	 * 空间进行优化：
	 * <p>
	 * f[i][j] = f[i-1][j]+f[i][j-1]
	 * 所以计算第i行时，只需要第i行和第i-1行的f,即空间复杂度O(2N)，即f[i][j]仅有当前行和上一行决定
	 * 通过滚动数组实现
	 * * 开数组时，只开f[0][0...n-1]和f[1][0...n-1]
	 * * 计算f[0][0],...,f[0][n-1],计算f[1][0],...,f[1][n-1]
	 * * 计算f[2][0...n-1]时，开f[2][0...n-1],删除f[0][0..n-1],因为已经不需要f[0][0...n-1]的值
	 * * 计算f[3][0...n-1]时，开f[2][0...n-1],删除f[1][0..n-1],因为已经不需要f[1][0...n-1]的值
	 * <p>
	 * 实际操作时，不用每次开/删数组，而是用滚动法
	 * <p>
	 * 计算f[0][0],...,f[0][n-1],计算f[1][0],...,f[1][n-1]
	 * 计算f[2][0..n-1]时，把值写在f[0][0...n-1]的数组中
	 * 同理，计算f[3][0..n-1]时，把值写在f[1][0...n-1]的数组中
	 * 最后，f[m-1][n-1]存储在f[0][n-1](或者f[1][n-1])里，直接输出。
	 */
	public int minPathSum(int[][] grid) {
		if (grid == null || grid.length == 0 || grid[0].length == 0) {
			return 0;
		}

		int m = grid.length;
		int n = grid[0].length;

		//存储结果 a[i][j]
		int[][] f = new int[2][n];

		// old前一行，now当前行
		int old = 1, now = 0;

		int i, j, t1, t2;

		for (i = 0; i < m; i++) {
			//每换一行时，交换old和now
			old = now;
			// 数组是滚动的，或者使用%2
			now = 1 - old;
			for (j = 0; j < n; j++) {
				if (i == 0 && j == 0) {
					f[now][j] = grid[i][j];
					continue;
				}
				f[now][j] = grid[i][j];

				if (i > 0) {
					t1 = f[old][j];
				} else {
					t1 = Integer.MAX_VALUE;
				}

				if (j > 0) {
					t2 = f[now][j - 1];
				} else {
					t2 = Integer.MAX_VALUE;
				}
				f[now][j] += Math.min(t1, t2);

			}
		}
		return f[now][n - 1];

	}

	public static void main(String[] args) {
		int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
		MinPathSum instance = new MinPathSum();
		System.out.println(instance.minPathSum(grid));
	}
}
